UVa/11282 - Mixing invitations/11282.cpp

   1 /*
   2   Problem: 11282 - Mixing invitations
   3   Author: Andrés Mejía-Posada
   4   (http://blogaritmo.factorcomun.org)
   5
   6   Algoritm: Combinatorics formula
   7  */
   8
   9 using namespace std;
  10 #include <algorithm>
  11 #include <iostream>
  12 #include <iterator>
  13 #include <sstream>
  14 #include <fstream>
  15 #include <cassert>
  16 #include <climits>
  17 #include <cstdlib>
  18 #include <cstring>
  19 #include <string>
  20 #include <cstdio>
  21 #include <vector>
  22 #include <cmath>
  23 #include <queue>
  24 #include <deque>
  25 #include <stack>
  26 #include <map>
  27 #include <set>
  28
  29 const int N = 20;
  30
  31 long long choose[N+1][N+1], d[N+1]; //d[i] = Number of derangements if i elements.
  32
  33 int main(){
  34     /* Binomial coefficients */
  35   for (int i=0; i<=N; ++i) choose[i][0] = choose[i][i] = 1;
  36   for (int i=1; i<=N; ++i)
  37     for (int j=1; j<i; ++j)
  38       choose[i][j] = choose[i-1][j-1] + choose[i-1][j];
  39
  40   /* Derangements */
  41   d[0] = 1, d[1] = 0;
  42   for (int i=2; i<=N; ++i) d[i] = (i-1)*(d[i-2] + d[i-1]);
  43
  44   int n, m;
  45   while (cin >> n >> m){
  46     long long ans = 0;
  47     for (int k=0; k<=m; ++k) ans += choose[n][k] * d[n-k];
  48     cout << ans << endl;
  49   }
  50   return 0;
  51 }
  52
  53 /*
  54   Explanation: Let f(n, k) = Number of permutations of n elements
  55   such that exactly k of them are in their correct position. For
  56   example, f(3, 1) = 3 which are {1,3,2}, {3,2,1} and {2,1,3}.
  57   Then the answer is sum for every 0 <= k <= m of f(n, k).
  58
  59   Let D(n) = Numbers of derangenents of n elements. Note that for
  60   every n we have f(n, 0) = D(n). And in general,
  61
  62   f(n, k) = choose(n, k) * D(n - k)
  63
  64   The idea behind this is that we "nail" k elements from the whole
  65   sequence of n elements in choose(n, k) ways and for each possi-
  66   bility we disorder completely the missing n - k elements in
  67   D(n - k) ways.
  68
  69   D(i) is computed using a recurrent function, although could also
  70   be found using inclusion-exclusion principle.
  71  */